The present invention relates to the field of digital signal processing, and more particularly to computation of an unordered Hadamard transform.
A great variety of systems may be characterized by the property that they receive a signal and perform one or more mathematical operations on the received signal. Such signal processing is common in diverse fields such as telecommunications, wireless telecommunications, cryptography, filtering, data analysis, and others. Examples of such mathematical operations include the Fourier transform, the Walsh transform, the (ordered and unordered) Hadamard transform, and the Walsh-Hadamard transform, among others.
The Walsh transform is used in many areas such as image processing and digital communications as a fast way to compute an approximation of the FFT (Fast Fourier Transform). Lately it has found applications in cryptography and in testing the randomness of pseudo-random sequences. The latter application may require the computation of the Walsh transform for large 1 dimensional data sets (sometimes of the order of a 1 billion numbers or more).
Definition of Walsh Transform
The Walsh Transform of a sequence f(x), x=0, . . . ,Nxe2x88x921 is defined as:                               W          ⁡                      (            u            )                          =                              (                          1              /              N                        )                    ⁢                                    ∑                              x                =                0                                            N                -                1                                      ⁢                                          f                ⁡                                  (                  x                  )                                            ⁢                                                ∏                                      l                    =                    0                                                        n                    -                    1                                                  ⁢                                                      (                                          -                      1                                        )                                                                                                      b                        i                                            ⁡                                              (                        x                        )                                                              ⁢                                                                  b                                                  n                          -                          l                          -                          1                                                                    ⁡                                              (                        u                        )                                                                                                                                                    (        1        )            
where bi(x) denotes the ith bit of x, and n=log2(N).
Similarly, the inverse Walsh transform is defined as:                               f          ⁡                      (            x            )                          =                              ∑                          u              =              0                                      N              -              1                                ⁢                                    W              ⁡                              (                u                )                                      ⁢                                          ∏                                  l                  =                  0                                                  n                  -                  1                                            ⁢                                                (                                      -                    1                                    )                                                                                            b                      i                                        ⁡                                          (                      x                      )                                                        ⁢                                                            b                                              n                        -                        l                        -                        1                                                              ⁡                                          (                      u                      )                                                                                                                              (        2        )            
The Hadamard Transform is similar to the Walsh transform and its transform matrix is actually a permutation of the Walsh transform matrix. The unordered Hadamard transform matrix may be constructed recursively for any length which is a power of 2, using a basic 2xc3x972 matrix H2 according to the relations:                                           H            2                    =                      [                                                                                                      +                      1                                        +                    1                                                                                                                                          +                      1                                        -                    1                                                                        ]                          ⁢                  
                ⁢                              H            4                    =                      [                                                                                                      +                                              H                        2                                                              +                                          H                      2                                                                                                                                                              +                                              H                        2                                                              -                                          H                      2                                                                                            ]                          ⁢                  
                ⁢                              H                          2              ⁢              N                                =                      [                                                                                                      +                                              H                        N                                                              +                                          H                      N                                                                                                                                                              +                                              H                        N                                                              -                                          H                      N                                                                                            ]                                              (        3        )            
For signal processing applications, the ordered Hadamard transform is primarily used:                               H          ⁡                      (            u            )                          =                              (                          1              /              N                        )                    ⁢                                    ∑                              x                =                0                                            N                -                1                                      ⁢                                          f                ⁡                                  (                  x                  )                                            ⁢                                                (                                      -                    1                                    )                                                                      ∑                                          l                      =                      0                                                              N                      -                      1                                                        ⁢                                                                                    b                        l                                            ⁡                                              (                        x                        )                                                              ⁢                                                                  b                        l                                            ⁡                                              (                        u                        )                                                                                                                                                    (        4        )                                          f          ⁡                      (            x            )                          =                              (                          1              /              N                        )                    ⁢                                    ∑                              u                =                0                                            N                -                1                                      ⁢                                          H                ⁡                                  (                  u                  )                                            ⁢                                                (                                      -                    1                                    )                                                                      ∑                                          l                      =                      0                                                              N                      -                      1                                                        ⁢                                                                                    b                        l                                            ⁡                                              (                        x                        )                                                              ⁢                                                                  b                        l                                            ⁡                                              (                        u                        )                                                                                                                                                    (        5        )            
It is noted that the Walsh and the ordered Hadamard transform are actually permutations of the unordered Hadamard transform, therefore once the unordered Hadamard transform has been computed, if the order of the results is important, they may be obtained by a simple reordering.
Mathematical operations such as these are typically performed on a received signal by a computer system with a single processor and memory (Von Neumann architecture). While this approach works well for small data sets (signals), the processing of much larger data sets may not be feasible due to time constraints.
To address the problems of processing large signals or data sets, algorithms have been developed for performing various signal processing operations via parallel computation systems, such as large matrix transpositions, for example. While a number of efficient methods for computation of the unordered Hadamard transform on a single CPU have been proposed, there are currently no known methods for parallel computation of the unordered Hadamard transform.
Thus, there exists a substantial need for a system and method for parallel computation of the unordered Hadamard transform.
Various embodiments of a system and method are presented for parallel computation of the unordered Hadamard transform. In the preferred embodiment, the method is performed by a computing system which includes a plurality of interconnected processors, each with a corresponding local memory. The method is presented in four stages for clarity.
In stage one, an input signal x is received and partitioned into a plurality of M1 sub-vectors xi, each having length M2. Thus, the signal x comprises M1xc3x97M2 elements or values. The sub-vectors are then distributed to the local memories of the computing system. In other words, one or more of the sub-vectors xi are distributed or assigned to each processor/local memory.
Each processor may then compute a Hadamard transform (order M2) on the one or more sub-vectors in its local memory. In the preferred embodiment, the processors compute their respective transforms in parallel. The transforms performed on the sub-vectors xi may generate a plurality of M1 result sub-vectors ti, each having length M2, which compose a distributed result vector t of length M1xc3x97M2.
In the second stage of the method, elements of the result vector t may be collected with a stride of M2 and placed into consecutively indexed locations in a second result vector u. In other words, a stride permutation may be performed on the result vector t (with stride M2) to generate result vector u. Said another way, the vector t may be considered or interpreted as a distributed M1xc3x97M2 matrix, where each result sub-vector ti is viewed as a column (or row) of the matrix. A parallel matrix transposition is then performed, resulting in a transposed M2xc3x97M1 matrix, i.e., a matrix comprised of M2 result sub-vectors uj, each of length M1.
In the third stage of the method, each processor may compute a Hadamard transform (order M1) on the one or more result sub-vectors uj in its local memory. In the preferred embodiment, the processors compute their respective transforms in parallel. The transforms performed on the sub-vectors generate a plurality of M2 result sub-vectors vj, each having length M1, which compose a distributed result vector v of length M2xc3x97M1.
In the fourth stage of the method, elements of the result vector v may be collected with a stride of M1 and placed into consecutively indexed locations in a final result vector w. In other words, a stride permutation is performed on the result vector v (with stride M1) to generate result vector w. Said another way, the vector v may be considered or interpreted as a distributed M2xc3x97M1 matrix, where each result sub-vector vj is viewed as a column (or row) of the matrix. A parallel matrix transposition is then performed, resulting in a transposed M1xc3x97M2 matrix, i.e., a matrix comprised of M1 result sub-vectors wi, each of length M2. The ordered sub-vectors wi compose a distributed vector w, which is the unordered Hadamard transform of the input signal x.
It should be noted that if the order of elements of the final result is unimportant, then the last stage may be omitted, because only the order of the values changes.